package com.leetcode.algorithm.y19.m03;

import java.util.ArrayList;
import java.util.List;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * 
 * (TODO)687. 最长同值路径
 * (TODO)662. 二叉树最大宽度
 * (TODO)655. 输出二叉树 
 * (TODO)507. 完美数
 * (TODO)754. 到达终点数字
 * (TODO)836. 矩形重叠
 * @author: jie.deng
 * @time: 2019年1月17日 下午2:31:26
 */
public class MySolutionToDo {
	
	/**
	 * 687. 最长同值路径
	 *
   	 * 给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
   	 * 
   	 * 注意：两个节点之间的路径长度由它们之间的边数表示。
   	 * 
   	 * 示例 1:
   	 * 
   	 * 输入:
   	 * 
   	 *               5
   	 *              / \
   	 *             4   5
   	 *            / \   \
   	 *           1   1   5
   	 * 输出:
   	 * 
   	 * 2
   	 * 示例 2:
   	 * 
   	 * 输入:
   	 * 
   	 *               1
   	 *              / \
   	 *             4   5
   	 *            / \   \
   	 *           4   4   5
   	 * 输出:
   	 * 
   	 * 2
   	 * 注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
	 * @param root
	 * @return
	 */
	public int longestUnivaluePath(TreeNode root) {
		return 0;
	}
	
    /**
     * 662. 二叉树最大宽度
     * 
     * 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
     * 
     * 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
     * 
     * 示例 1:
     * 
     * 输入: 
     * 
     *            1
     *          /   \
     *         3     2
     *        / \     \  
     *       5   3     9 
     * 
     * 输出: 4
     * 解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
     * 示例 2:
     * 
     * 输入: 
     * 
     *           1
     *          /  
     *         3    
     *        / \       
     *       5   3     
     * 
     * 输出: 2
     * 解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
     * 示例 3:
     * 
     * 输入: 
     * 
     *           1
     *          / \
     *         3   2 
     *        /        
     *       5      
     * 
     * 输出: 2
     * 解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
     * 示例 4:
     * 
     * 输入: 
     * 
     *           1
     *          / \
     *         3   2
     *        /     \  
     *       5       9 
     *      /         \
     *     6           7
     * 输出: 8
     * 解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。
     * 注意: 答案在32位有符号整数的表示范围内。
     * @param root
     * @return
     */
    public int widthOfBinaryTree(TreeNode root) {
		return 0;
    }
    
    /**
     * 655. 输出二叉树
     * 
     * 在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：
     * 
     * 行数 m 应当等于给定二叉树的高度。
     * 列数 n 应当总是奇数。
     * 根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。
     * 每个未使用的空间应包含一个空的字符串""。
     * 使用相同的规则输出子树。
     * 示例 1:
     * 
     * 输入:
     *      1
     *     /
     *    2
     * 输出:
     * [["", "1", ""],
     *  ["2", "", ""]]
     * 示例 2:
     * 
     * 输入:
     *      1
     *     / \
     *    2   3
     *     \
     *      4
     * 输出:
     * [["", "", "", "1", "", "", ""],
     *  ["", "2", "", "", "", "3", ""],
     *  ["", "", "4", "", "", "", ""]]
     * 示例 3:
     * 
     * 输入:
     *       1
     *      / \
     *     2   5
     *    / 
     *   3 
     *  / 
     * 4 
     * 输出:
     * [["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
     *  ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
     *  ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
     *  ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]
     * 注意: 二叉树的高度在范围 [1, 10] 中。
     * @param root
     * @return
     */
    public List<List<String>> printTree(TreeNode root) {
		return null;
    }
    
	/**
	 * 507. 完美数
	 * 
	 * 对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。
	 * 
	 * 给定一个 正整数 n， 如果他是完美数，返回 True，否则返回 False
	 * 
	 * 
	 * 
	 * 示例：
	 * 
	 * 输入: 28 输出: True 解释: 28 = 1 + 2 + 4 + 7 + 14
	 * 
	 * 
	 * 注意:
	 * 
	 * 输入的数字 n 不会超过 100,000,000. (1e8)
	 * 
	 * @param num
	 * @return
	 */
	public boolean checkPerfectNumber(int num) {
		return false;
	}
	
	/**
	 * 836. 矩形重叠
	 * 
	 * 矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。
	 * 
	 * 如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
	 * 
	 * 给出两个矩形，判断它们是否重叠并返回结果。
	 * 
	 * 示例 1：
	 * 
	 * 输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3] 输出：true 示例 2：
	 * 
	 * 输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1] 输出：false 说明：
	 * 
	 * 两个矩形 rec1 和 rec2 都以含有四个整数的列表的形式给出。 矩形中的所有坐标都处于 -10^9 和 10^9 之间。
	 */
	public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
		// 矩形的4个点，相交则至少有一个点在另一个矩形内部
		// (rec1[0],rec1[1])、(rec1[0],rec1[3])、(rec1[2],rec1[1])、(rec1[2],rec1[3])
		// (rec2[0],rec2[1])、(rec2[0],rec2[3])、(rec2[2],rec2[1])、(rec2[2],rec2[3])

		// (rec1[0],rec1[1])、(rec1[0],rec1[3])
		if (rec1[0] > rec2[0] && rec1[0] < rec2[2]) {
			// (rec1[0],rec1[1])
			if (rec1[1] > rec2[1] && rec1[1] < rec2[3]) {
				return true;
			}
			// (rec1[0],rec1[3])
			if (rec1[3] > rec2[1] && rec1[3] < rec2[3]) {
				return true;
			}
		}
		// (rec1[2],rec1[1])、(rec1[2],rec1[3])
		if (rec1[2] > rec2[0] && rec1[2] < rec2[2]) {
			// (rec1[2],rec1[1])
			if (rec1[1] > rec2[1] && rec1[1] < rec2[3]) {
				return true;
			}
			// (rec1[2],rec1[3])
			if (rec1[3] > rec2[1] && rec1[3] < rec2[3]) {
				return true;
			}
		}

		// (rec2[0],rec2[1])、(rec2[0],rec2[3])
		if (rec2[0] > rec1[0] && rec2[0] < rec1[2]) {
			// (rec2[0],rec2[1])
			if (rec2[1] > rec1[1] && rec2[1] < rec1[3]) {
				return true;
			}
			// (rec2[0],rec2[3])
			if (rec2[3] > rec1[1] && rec2[3] < rec1[3]) {
				return true;
			}
		}
		// (rec2[2],rec2[1])、(rec2[2],rec2[3])
		if (rec2[2] > rec1[0] && rec2[2] < rec1[2]) {
			// (rec2[2],rec2[1])
			if (rec2[1] > rec1[1] && rec2[1] < rec1[3]) {
				return true;
			}
			// (rec2[2],rec2[3])
			if (rec2[3] > rec1[1] && rec2[3] < rec1[3]) {
				return true;
			}
		}

		return false;
	}
	
    
}
